/**
 * 279. 完全平方数
 * https://leetcode-cn.com/problems/perfect-squares/
 */

/**
 * @param {number} n
 * @param {number[]} squares
 * @param {number[]} cache
 * @return {number}
 */
function cal(n, squares, cache) {
  if (cache[n]) {
    return cache[n];
  }
  const middle = n / 2;
  let min = Infinity;
  for (let i = 0; i < squares.length && squares[i] <= middle; i += 1) {
    min = Math.min(min, cal(n - squares[i], squares, cache) + 1);
  }
  cache[n] = min;
  return min;
}

/**
 * @param {number} n
 * @return {number}
 */
function numSquares(n) {
  const end = Math.floor(Math.sqrt(n));
  const cache = new Array(n + 1);
  const squares = new Array(end);
  for (let i = 1; i <= end; i += 1) {
    const num = i * i;
    squares[i - 1] = num;
    cache[num] = 1;
  }
  return cal(n, squares, cache);
}

console.log(numSquares(12) === 3);
console.log(numSquares(13) === 2);
